import java.util.Scanner;

public class Test1 {
//    求斐波那契数列的第 n 项
//    求斐波那契数列不建议使用递归，因为会存在大量的重复运算
//    运用循环(迭代)来做可以避免大量的重复运算

    public static int fib2(int n){
        if(n == 1 || n == 2){
            return 1;
        }
        int f1 = 1;
        int f2 = 1;
        int f3 = 0;
        for(int i = 3;i <= n;i++){
            f3 = f1 + f2;
            f1 = f2;
            f2 = f3;
        }
        return f3;
    }


    static int count = 0;
    public static int fib1(int n){
        if(n == 1 || n == 2){
            count++;
            return 1;
        }
        return fib1(n - 1) + fib1(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fib1(40));
        System.out.println(count);
        System.out.println(fib2(10));
    }




//    写一个非负整数，求每位之和

    public static int intSum(int n){
        if(n < 10){
            return n;
        }
        int ret = n % 10;
        return ret + intSum(n / 10);
    }

    public static void main4(String[] args) {
        System.out.println(intSum(1729));
    }




//    递归求 1 - 10 的和

    public static int sum(int n){
        if(n == 1){
            return 1;
        }
        return n + sum(n - 1);
    }


    public static void main3(String[] args) {
        int ret = sum(10);
        System.out.println(ret);
    }




//    打印每位数

    public static void fanc(int n){
        if(n < 10){
            System.out.println(n);
            return;
        }
        fanc(n / 10);
        System.out.println(n % 10);
    }

    public static void main2(String[] args) {
        fanc(12345);
}



//    递归
    public static int fac(int n){
        if(n == 1){
            return 1;
        }
        return n * fac(n - 1);
    }

    public static void main1(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();

        System.out.println(fac(n));
    }
}
